#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<ctime>
using namespace std;

template <typename Comparable>
class BinarySearchTree
{
 public:
	BinarySearchTree();
	BinarySearchTree(const BinarySearchTree & rhs);
	~BinarySearchTree();
	bool contains(const Comparable & x) const;
	void insert(const Comparable & x);
	void insert(Comparable&& x)
	{
		insert(x, root);
	}
	void makeEmpty();
	void remove(const Comparable& x)
	{
		remove(x, root);
	}
	const Comparable& findMin() const
	{
		if (findMin(root) == nullptr)  return 0;
		else    return findMin(root)->element;
	}


private:
	struct BinaryNode
	{
		Comparable element;
		BinaryNode * left;
		BinaryNode * right;
		BinaryNode(const Comparable & theElement, BinaryNode * lt, BinaryNode * rt)
			: element{ theElement }, left{ lt }, right{ rt } { }
		BinaryNode(Comparable && theElement, BinaryNode * lt, BinaryNode * rt)
			: element{ std::move(theElement) }, left{ lt }, right{ rt } { }
	};
		BinaryNode * root;
		void insert(const Comparable & x, BinaryNode * &t);
		void insert(Comparable && x, BinaryNode * &t);
		void remove(const Comparable& x, BinaryNode*& t);
		BinaryNode* findMin(BinaryNode* t) const
		{
			if (t == nullptr)
				return nullptr;
			if (t->left == nullptr)
				return t;
			return findMin(t->left);
		}
		bool contains(const Comparable & x, BinaryNode * t) const;
		void makeEmpty(BinaryNode * &t);
		BinaryNode* clone(BinaryNode* t) const
		{
			if (t == nullptr)
				return nullptr;
			else
				return new BinaryNode{ t->element, clone(t->left), clone(t->right) };
		}
};
	template<typename Comparable>
	BinarySearchTree<Comparable>::BinarySearchTree()
	{
		root = nullptr;
	}
	/**
	 * Returns true if x is found in the tree.
	 */
	template<typename Comparable>
	bool BinarySearchTree<Comparable>::contains(const Comparable & x) const
	{
		return contains(x, root);
	}
 
	/**
	 * Insert x into the tree; duplicates are ignored.
	 */
	template<typename Comparable>
	void BinarySearchTree<Comparable>::insert(const Comparable & x)
	{
		insert(x, root);
	}
	template<typename Comparable>
	void BinarySearchTree<Comparable>::makeEmpty()
	{
		makeEmpty(root);
	}

	/**
	* Internal method to test if an item is in a subtree.
	* x is item to search for.
	* t is the node that roots the subtree.
	*/
	template<typename Comparable>
	bool BinarySearchTree<Comparable>::contains(const Comparable & x, BinaryNode * t) const
	{
		if (t == nullptr)
			return false;
		else if (x < t->element)
			return contains(x, t->left);
		else if (t->element < x)
			return contains(x, t->right);
		else
			return true; // Match
	}
	/**
	* Internal method to insert into a subtree.
	* x is the item to insert.
	* t is the node that roots the subtree.
	* Set the new root of the subtree.
	*/
	template<typename Comparable>
	void BinarySearchTree<Comparable>::insert(const Comparable & x, BinaryNode * &t)
	{
		if (t == nullptr)
			t = new BinaryNode{ x, nullptr, nullptr };
		else if (x < t->element)
			insert(x, t->left);
		else if (t->element < x)
			insert(x, t->right);
		else
			;// Duplicate; do nothing
	}
	/**
	* Internal method to insert into a subtree.
	* x is the item to insert by moving.
	* t is the node that roots the subtree.
	* Set the new root of the subtree.
	*/
	template<typename Comparable>
	void BinarySearchTree<Comparable>::insert(Comparable&& x, BinaryNode*& t)
	{
		if (t == nullptr)
			t = new BinaryNode{ std::move(x), nullptr, nullptr };
		else if (x < t->element)
			insert(std::move(x), t->left);
		else if (t->element < x)
			insert(std::move(x), t->right);
		else
			;// Duplicate; do nothing
	}
	/**
	* Destructor for the tree
	*/
	template<typename Comparable>
	BinarySearchTree<Comparable>::~BinarySearchTree()
	{
		makeEmpty();
	}
	/**
	* Internal method to make subtree empty.
	*/
	template<typename Comparable>
	void BinarySearchTree<Comparable>::makeEmpty(BinaryNode * &t)
	{
		if (t != nullptr)
		{
			makeEmpty(t->left);
			makeEmpty(t->right);
			delete t;
		}
		t = nullptr;
	}
	/**
	* Copy constructor
	*/
	template<typename Comparable>
	BinarySearchTree<Comparable>::BinarySearchTree(const BinarySearchTree & rhs) : root{ nullptr }
	{
		root = clone(rhs.root);
	}
	/**
	* Internal method to remove from a subtree.
	* x is the item to remove.
	* t is the node that roots the subtree.
	* Set the new root of the subtree.
	*/
	template<typename Comparable>
	void BinarySearchTree<Comparable>::remove(const Comparable & x, BinaryNode * &t)
	{
		if (t == nullptr)
			return; // Item not found; do nothing
		if (x < t->element)
			remove(x, t->left);
		else if (t->element < x)
			remove(x, t->right);
		else if (t->left != nullptr && t->right != nullptr) // Two children
		{
			t->element = findMin(t->right)->element;
			remove(t->element, t->right);
		}
		else
		{
			BinaryNode * oldNode = t;
			t = (t->left != nullptr) ? t->left : t->right;
			delete oldNode;
		}
		}
    //全局函数，从空树开始依次插入
	template<typename Comparable>
	void BST_sort(std::vector<Comparable>& _data, BinarySearchTree<Comparable> & b)
	{
		for (unsigned int i = 0; i <_data.size(); i++)
		{
			b.insert(_data[i]);
			
		}
	}
    //打乱数组
	template<typename Comparable>
	void Randomized_BST_sort(std::vector<Comparable>& _data)
	{
		int len = _data.size();
		for (int i = len - 1; i >= 0; i--)
		{
			int a = _data.size();
			srand((int)time(0));
			int randomindex = (rand() % (a - 1));
			Comparable temp = _data[randomindex];
			_data[randomindex] = _data[i];
			_data[i] = temp;
		}
	}

	
